home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / hotjava3 / hotjava3.exe / hotjava / classsrc / browser / tools / JavaSearch / Index.java < prev    next >
Encoding:
Java Source  |  1995-08-11  |  8.1 KB  |  284 lines
  1. /*
  2.  * @(#)Index.java    1.15 95/03/14 David A. Brown
  3.  *
  4.  * Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
  5.  *
  6.  * Permission to use, copy, modify, and distribute this software
  7.  * and its documentation for NON-COMMERCIAL purposes and without
  8.  * fee is hereby granted provided that this copyright notice
  9.  * appears in all copies. Please refer to the file "copyright.html"
  10.  * for further important copyright and licensing information.
  11.  *
  12.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  13.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  14.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  15.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  16.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  17.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  18.  */
  19.  
  20. package browser.tools.JavaSearch;
  21. import java.util.*;
  22. import java.io.*;
  23. //import javaindex;
  24.  
  25. /**
  26.  * Index: the master word/doc inverted index for an JavaSearch
  27.  *         database.  Basically a collection of index entries, along
  28.  *         with some * functionality to manipulate them.
  29.  *
  30.  *     Important: This class is only used when BUILDING an JavaSearch
  31.  *         index; when doing a search, the Searcher object directly
  32.  *         reads the on-disk .index and .qindex files.
  33.  *
  34.  *   REMIND:  This class needs a couple of serious
  35.  *     optimizations!  (Especially look for "btree"
  36.  *     comments below...)
  37.  *
  38.  */
  39. class Index {
  40.  
  41.     //
  42.     // Various tweakable indexing parameters
  43.     //
  44.     /** Shortest word we will index */
  45.     static final int MIN_WORD_LENGTH = 2;
  46.  
  47.     //
  48.     // Misc constants
  49.     //
  50.     /** Header ('magic number') at top of index files */
  51.     static final String indexFileHeader = "JavaSearch-index";
  52.  
  53.  
  54.     /** 
  55.      * All the words in this Index.  This is a Vector of Word objects.
  56.      * This is only used 
  57.      */
  58.     Vector entries;
  59.     Hashtable table;    // changed vector to use hashtable instead
  60.  
  61.     StopList stopList = null;
  62.     
  63.     /** Create a new, empty index */
  64.     public Index(String stopfile) {
  65.     System.out.println("Index constructor...");
  66.     //entries = new Vector();
  67.         table = new Hashtable();
  68.  
  69.     try {
  70.         if (stopfile != null) {
  71.         stopList = new StopList(stopfile);
  72.         }
  73.     } catch (IOException e) {
  74.         System.err.println("No such stop list file - \""+stopfile+"\"");
  75.         System.err.println("Ignoring stop list.");
  76.         stopList = null;
  77.     }
  78.     }
  79.  
  80.  
  81.     /**
  82.      *  Add all the words we find in the specified IndexingInputStream
  83.      *  to the Index, associating them with the specified Doc.
  84.      */
  85.     public void addDocToIndex(Doc doc, IndexingInputStream in) {
  86.     String word;
  87.     int startTime = System.nowMillis();
  88.  
  89.     Hashtable seenInDoc = new Hashtable();
  90.     
  91.     while ((word = in.getWord()) != null) {
  92.         //System.out.println("  word: '"+word+"'");
  93.         if ((word.length() >= MIN_WORD_LENGTH) &&
  94.         (!stopList.isStopWord(word))) {
  95.         if (seenInDoc.get(word) == null) {
  96.             seenInDoc.put(word, word);
  97.  
  98.             // It's not a stopword, too short, or already
  99.             // seen in this document, so add word to index.
  100.             
  101.             //System.out.println("adding index entry: '"+word+"'");
  102.             
  103.             Word w = getWord(word);
  104.             if (w == null) {
  105.             w = addWord(word);
  106.             }
  107.             w.idvector.appendID(doc.docID);
  108.         }
  109.         }
  110.     }
  111.  
  112.     int totalTime = System.nowMillis() - startTime;
  113.     javaindex.parseTime += totalTime;
  114.     }
  115.  
  116.     /** 
  117.      *  Return the Word in our entries Vector for the
  118.      *  specified word, or null if we don't have an entry for 'word'.
  119.      */
  120.     public Word getWord(String word) {
  121.  
  122.     // REMIND:  This is terrible!  When we're indexing, we
  123.     //   should store the Words we're accumulating in memory
  124.     //   in a btree, not in an unsorted Vector!!!
  125.     //     (Sorry, I didn't get around to implementing
  126.     //     a btree utility class.  But this only makes
  127.     //     indexing slow, not searching...   - dab )
  128.     
  129.         Word w = (Word)table.get(word);
  130.         return w;
  131. /* change to hashtable
  132.     for (int i=0; i<entries.size(); i++) {
  133.         Word w = (Word)entries.elementAt(i);
  134.         if (w.word.equals(word)) {
  135.         return w;
  136.         }
  137.     }
  138.     return null;
  139. */
  140.     }
  141.  
  142.     /**
  143.      * Create a Word object for the specified word,
  144.      * and add it to our entries Vector.  Don't call this
  145.      * unless you're sure we don't already have a Word object
  146.      * for this word!
  147.      */
  148.     public Word addWord(String word) {
  149.  
  150.     Word w = new Word(word);
  151.  
  152.         table.put(word, w);
  153. /* change to hashtable
  154.     // REMIND:  We really should be inserting the Word into
  155.     //   a btree here!
  156.     entries.addElement(w);
  157. */
  158.     return w;
  159.     }
  160.  
  161.  
  162.     /**
  163.      *  Sort the 'entries' vector alphabetically by each
  164.      *    entry's word.
  165.      *
  166.      *    REMIND:  This would be unnecessary if we used
  167.      *             a btree to hold our Words...
  168.      */
  169.     public void sort() {
  170.     System.out.print("Sorting index...  ");
  171.     int starttime = System.nowMillis();
  172.     // An entry is    Word w = (Word)entries.elementAt(i);
  173.     // An entry's word is  w.word
  174.  
  175.         // copy the hashtable into a vector
  176.         int tableSize = table.size();
  177.         entries = new Vector(tableSize);
  178.         Enumeration enumeration = table.elements();
  179.         for (int i=0; i<tableSize; i++) {
  180.             entries.addElement(enumeration.nextElement());
  181.         }
  182.  
  183.     qsort_entries(0, entries.size()-1);
  184.  
  185.     int sortTime = System.nowMillis() - starttime;
  186.     System.out.println("Done. Time to sort: " + sortTime + " ms.");
  187.     javaindex.numSorts++;
  188.     javaindex.sortTime += sortTime;
  189.     }
  190.  
  191.     /** Guts of the qsort algorithm. 
  192.      *  Stolen from jag's QSortAlgorithm.java demo */
  193.     private void qsort_entries(int lo0, int hi0) {
  194.         int lo = lo0;
  195.         int hi = hi0;
  196.         if (lo >= hi)
  197.             return;
  198.         String mid = ((Word)entries.elementAt((lo + hi) / 2)).word;
  199.         while (lo < hi) {
  200.             while (lo<hi && (((Word)entries.elementAt(lo)).word.compareTo(mid) < 0))
  201.         lo++;
  202.             while (lo<hi && (((Word)entries.elementAt(hi)).word.compareTo(mid) > 0))
  203.                 hi--;
  204.             if (lo < hi) {
  205.         Word w_lo = (Word)entries.elementAt(lo);
  206.         Word w_hi = (Word)entries.elementAt(hi);
  207.         entries.setElementAt(w_lo,hi);
  208.         entries.setElementAt(w_hi,lo);
  209.             }
  210.         }
  211.         if (hi < lo) {
  212.             int T = hi;
  213.             hi = lo;
  214.             lo = T;
  215.         }
  216.         qsort_entries(lo0, lo);
  217.         qsort_entries(lo == lo0 ? lo+1 : lo, hi0);
  218.     }
  219.  
  220.  
  221.  
  222.  
  223.     /** Print out the full contents of this index.  For debuggging. */
  224.     public void dump() {
  225.     System.out.println("Index.dump():  This index contains "+entries.size()+" entries.");
  226.  
  227.     for (int i=0; i<entries.size(); i++) {
  228.             Word w = (Word)entries.elementAt(i);
  229.         System.out.println("  "+i+"\t"+w);
  230.         }
  231.     System.out.println("-----");
  232.     }
  233.  
  234.  
  235.  
  236.  
  237.     /**
  238.      * Save this JavaSearch index to disk, as part of the database 'db'.
  239.      * Returns the total size of the .index file.
  240.      */
  241.     public void saveAs(Database db) {
  242.     System.out.println("Index.saveAs()...");
  243.  
  244.     // Ensure we're sorted.  No big deal if someone already
  245.     //   manually called sort() since qsort is reasonably fast
  246.     //   if we're already sorted.
  247.     sort();
  248.  
  249.     // Open two output streams (index + qindex).
  250.     // Write each Word to the .index file, and for
  251.     //   each one add a position entry to the .qindex file.
  252.     //
  253.     System.out.println("Opening index file '" + db.indexFilename + "'...");
  254.     FileOutputStream fileout = new FileOutputStream(db.indexFilename);
  255.     DataOutputStream out = new DataOutputStream(fileout);
  256.     //
  257.     System.out.println("Opening qindex file '" + db.qindexFilename + "'...");
  258.     FileOutputStream qfileout = new FileOutputStream(db.qindexFilename);
  259.     DataOutputStream qout = new DataOutputStream(qfileout);
  260.  
  261.     // Write some header info.
  262.     // Future:  version numbers?  other db or index info?
  263.     out.writeBytes(indexFileHeader);
  264.     out.writeByte('\n');
  265.  
  266.     // Ok, just write every Word in order...
  267.     for (int i=0; i<entries.size(); i++) {
  268.         int outPos = out.size();
  269.             Word w = (Word)entries.elementAt(i);
  270.         w.writeToStream(out);
  271.         // Write the qindex record
  272.         qout.writeInt(outPos);
  273.     }
  274.     int indexSize = out.size();
  275.     fileout.close();
  276.     qfileout.close();
  277.     System.out.println("Wrote index file ("+indexSize+" bytes).");
  278.     }
  279.  
  280.  
  281.  
  282.  
  283. }
  284.